package 滑动窗口;

import java.util.*;

public class LeetCode438_找到字符串中所有字母异位词 {
    public static List<Integer> findAnagrams_mingge(String s, String p) {
        List<Integer> list = new LinkedList<Integer>();
        if(s == null || p == null || s.length() < p.length()) {
            return list;
        }
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for(int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i)-'a'] ++;
            pCount[p.charAt(i)-'a'] ++;
        }
        if(Arrays.equals(sCount,pCount)) {
            list.add(0);
        }
        for(int i = 0;i < s.length() - p.length(); i++) {
            sCount[s.charAt(i)-'a']--;
            sCount[s.charAt(i+p.length())-'a']++;

            if(Arrays.equals(sCount,pCount)) {
                list.add(i+1);
            }
        }
        return list;
    }
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<Integer>();
        Map<Character,Integer> map = new HashMap<Character,Integer>();
        if(s == null || p == null || s.length() < p.length()) {
            return list;
        }

        int length = p.length();
        int left = 0;
        int right = length - 1;
        while(right < s.length()) {
            for (int i = 0; i < p.length(); i++) {
                map.put(p.charAt(i), map.getOrDefault(p.charAt(i),0)+1);
            }
            for(int i = left; i <= right; i++) {
                if((map.containsKey(s.charAt(i))) && map.get(s.charAt(i)) > 0) {
                    map.put(s.charAt(i), map.get(s.charAt(i))-1);
                    if(i == right) {
                        list.add(left);
                        map.clear();
                    }
                }else {
                    map.clear();
                    break;
                }
            }
            left++;
            right++;
        }
        return list;
    }

    public static void main(String[] args) {
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> list = findAnagrams(s,p);
        System.out.println(list);
    }
}
